#include <cstdio>
#include <map>
#include <cstring>
#include <string>
#include <iostream>

using namespace std;

int g[1010][1010];
int n, m, limit;
int num;
map< string, int > wh;
bool use[1010], ok[1010];
int minn[1010][2], maxx[1010][3];
int from[1010], fa[1010];
int dist[1010];
int ans;

void prim( int x ){
	use[x]=true; from[x]=++num;
	for ( int j=2; j<=n; j++ ){
		dist[j]=g[x][j]; fa[j]=x;
	}
	for ( int j=2; j<=n; j++ ){
		int minn=100000000, q;
		for ( int k=2; k<=n; k++ )
			if ( dist[k]!=0 && dist[k]<minn ){
				minn=dist[k]; q=k;
			}
		if ( minn==100000000 ) break;
		from[q]=num; ans+=dist[q]; use[q]=true; dist[q]=0;
		g[fa[q]][q]=g[q][fa[q]]=-g[fa[q]][q];
		for ( int k=2; k<=n; k++ )
			if ( ! use[k] && g[q][k]!=0 )
				if ( dist[k]==0 || g[q][k]<dist[k] ){
					dist[k]=g[q][k]; fa[k]=q;
				}
	}
}

void dfs( int x ){
	use[x]=true;
	for ( int j=2; j<=n; j++ )
		if ( g[x][j]<0 && ! use[j] ){
			if ( g[x][j]<maxx[x][0] ){
				maxx[j][0]=g[x][j]; maxx[j][1]=x; maxx[j][2]=j; dfs(j);
			} else {
				maxx[j][0]=maxx[x][0]; maxx[j][1]=maxx[x][1]; maxx[j][2]=maxx[x][2]; dfs(j);
			}
		}
}

int main(){
	n=1; wh["Park"]=1;
	memset( g, 0, sizeof( g ) );
	scanf("%d\n", &m);
	for ( int i=0; i<m; i++ ){
		string s1, s2;
		int l;
		cin>>s1>>s2>>l;
		if ( wh[s1]==0 )
			wh[s1]=++n;
		if ( wh[s2]==0 )
			wh[s2]=++n;
		g[wh[s1]][wh[s2]]=g[wh[s2]][wh[s1]]=l;
	}
	scanf("%d", &limit);
	ans=0;
	for ( int i=2; i<=n; i++ )
		if ( ! use[i] )
			prim(i);
	for ( int i=1; i<=n; i++ )
		minn[i][0]=100000000;
	for ( int i=2; i<=n; i++ ){
		if ( g[i][1] && g[i][1]<minn[from[i]][0] ){
			minn[from[i]][0]=g[i][1]; minn[from[i]][1]=i;
		}
		g[i][1]=-g[i][1]; g[1][i]=-g[1][i];
	}
	memset( ok, false, sizeof( ok ) );
	for ( int i=1; i<=num; i++ ){
		ans+=minn[i][0]; ok[minn[i][1]]=true;
	}
	for ( int i=2; i<=n; i++ )
		if ( g[i][1]==0 ) ok[i]=true;
	memset( use, false, sizeof( use ) );
	for ( int i=2; i<=n; i++ )
		if ( ok[i] ){
			maxx[i][0]=100000000; dfs(i);
		}
	for ( int i=0; i<limit-num; i++ ){
		int k=0, p;
		for ( int j=2; j<=n; j++ )
			if ( ! ok[j] && g[j][1]-maxx[j][0]>k ){
				k=g[j][1]-maxx[j][0]; p=j;
			}
		if ( k>0 ){
			ans-=k;
			g[maxx[p][1]][maxx[p][2]]=0;
			g[maxx[p][2]][maxx[p][1]]=0;
			ok[p]=true;
		} else
			break;
		memset( use, false, sizeof( use ) );
		dfs(p);
	}
	printf("Total miles driven: %d\n", ans);
}
